package tree;

import java.util.Arrays;

/**
 * 堆：完全二叉树,最大堆和最小堆，常用于优先队列（每次弹出最大或最小值），数组存储
 * 插入、删除时间复杂度为O(logN)
 *
 *  建堆两种方式：
 *     1.逐个插入法（向上调整） 时间复杂度O(NlogN)
 *     2.批量插入（向下调整）时间复杂度O(N)
 *
 *  插入、删除时间复杂度都是O(N)
 *
 */

public class HeapS {

    private int[] elements;
    private int usedSize;

    //逐个插入建堆
    public HeapS(int capacity) {
        this.elements = new int[capacity];
        this.usedSize = 0;
    }

    //批量建堆
    public HeapS(int[] elements) {
        this.elements = elements;
        this.usedSize = elements.length;

        for (int i = (usedSize -2) / 2; i >= 0 ; i--) {
            shiftDown(i);
        }

    }
    //下沉
    private void shiftDown(int parentIndex ) {
        int childIndex = parentIndex * 2 + 1;

        while (childIndex < usedSize){
            //如果右孩子大，就用右孩子
            if(childIndex + 1 < usedSize && elements[childIndex+1] > elements[childIndex]){
                childIndex++;
            }
            if(elements[childIndex] > elements[parentIndex]){
                swap(childIndex, parentIndex);
                parentIndex = childIndex;
                childIndex = parentIndex * 2 + 1;
            }else{
                break;
            }

        }

    }

    //逐个插入
    public void insert(int value) {
        //判断容量是否足够，不够扩容
        sureCapacity();
        elements[usedSize] = value;

        //上浮
        shiftUp(usedSize);

        usedSize++;
    }

    //上浮操作
    private void shiftUp(int curSize) {
        int parent = (curSize - 1) / 2;
        while (curSize > 0 && elements[parent] < elements[curSize]) {
            swap(parent,curSize);
            curSize = parent;
            parent = (curSize - 1) / 2;
        }
    }



    //交换
    private void swap(int parent, int curSize) {
        int temp = elements[parent];
        elements[parent] = elements[curSize];
        elements[curSize] = temp;
    }

    public int poll(){
        if(usedSize == 0) return -1;
        int value = elements[0];
        swap(0, usedSize -1);
        usedSize--;
        shiftDown(0);
        return value;
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }

    /**
     *
     * 判断容量是否足够，不够扩容两倍
     *
     */
    private void sureCapacity() {
        if (usedSize == elements.length ) {
            elements = Arrays.copyOf(elements, elements.length * 2);
        }
    }

    public static void main(String[] args) {
        //逐个插入
        HeapS heapS = new HeapS(10);
        heapS.insert(10);
        heapS.insert(2);
        heapS.insert(33);
        heapS.insert(14);
        heapS.insert(18);
//        System.out.println(Arrays.toString(hs.elements));

//        int[] elements = {1,3,10,2,20};
//        HeapS heapS = new HeapS(elements);
        while (!heapS.isEmpty()) {
            System.out.println(heapS.poll());
        }
    }

}
